package com.formula.datastructure.question.tree;

// 计算宽度
public class Quest06 {
    public static void main(String[] args) {
        Node06 root = new Node06(1);
        Node06 a1 = new Node06(42);
        Node06 a2 = new Node06(45);
        Node06 b1 = new Node06(39);
        Node06 b2 = new Node06(31);
        Node06 b3 = new Node06(35);
        Node06 b4 = new Node06(34);

        Node06 c1 = new Node06(21);

        root.leftChild = a1;
        root.rightChild = a2;

        a1.leftChild = b1;
        a1.rightChild = b2;
        a2.leftChild = b3;
        a2.rightChild = b4;

        b3.rightChild = c1;

        Tree06 tree = new Tree06(root);
        System.out.println(tree.levelOrder());
    }
}

class Tree06 {
    private Node06 root;
    private int front;
    private int rear;
    private Layer06[] queue;

    public Tree06(Node06 root) {
        this.root = root;
    }

    public int getSize() {
        int count = 0;
        if (root != null) {
            return root.getSize(count);
        }
        return 0;
    }

    public int levelOrder() {
        queue = new Layer06[getSize()];
        front = 0;
        rear = 0;
        if (root != null) {
            Layer06 rootLayer = new Layer06(1, root);
            queue[rear++] = rootLayer;
            while (front < rear) {
                Node06 current = queue[front].node;
                int layerNo = queue[front].layer;
                // Pay attent to this line
                front++;
                System.out.println(current.data);
                if (current.leftChild != null) {
                    queue[rear++] = new Layer06(layerNo + 1, current.leftChild);
                }
                if (current.rightChild != null) {
                    queue[rear++] = new Layer06(layerNo + 1, current.rightChild);
                }
            }
        }
        return calWidth();
    }

    private int calWidth() {
        int sum = 0;
        int max = sum;
        int lastLayerNo = queue[0].layer;
        for (int i = 1; i < getSize(); i++) {
            if (lastLayerNo == queue[i].layer) {
                sum++;
            } else {
                lastLayerNo = queue[i].layer;
                sum = 1;
            }
            if (sum > max) {
                max = sum;
            }
        }
        return max;
    }
}

class Layer06 {
    public int layer;
    public Node06 node;

    public Layer06(int layer, Node06 node) {
        this.layer = layer;
        this.node = node;
    }
}

class Node06 {
    public Integer data;
    public Node06 leftChild;
    public Node06 rightChild;
    private int size;

    public Node06(Integer data) {
        this.data = data;
    }

    public int getSize(int count) {
        ++count;
        if (leftChild != null) {
            count = leftChild.getSize(count);
        }
        if (rightChild != null) {
            count = rightChild.getSize(count);
        }
        return count;
    }

}



